package com.future;

/**
 * Description: 371. 两整数之和
 * 对于二进制的加法运算，若不考虑进位，则 1+1=0，1+0=1，0+1=1，0+0=0，不难发现，结果等同于异或运算。
 * 因而排除进位，加法可用异或来实现。然后考虑进位，0+0 进位为 0，1+0 进位为 0，0+1 进位为 0，1+1 进位为1，结果等同于与运算。
 * 设 a，b 为两个二进制数，a^b 是不考虑进位时加法结果。当二进制位同时为 1 时，才有进位，
 * 因此 (a&b)<<1 是进位产生的值，称为进位补偿。将两者相加便是完整的加法结果。
 * 因此 a+b = a^b + (a&b)<<1。
 * 那么加法运算可以这样实现：
 * （1）先不考虑进位，按位计算各位累加（用异或实现），得到值 a；
 * （2）然后再考虑进位，并将进位的值左移，得值 b。如果 b 不为 0 与 a 值继续相加。如果 b 为 0，则 a 就是加法运算的结果。此过程可循环或递归实现。
 *
 * @author weiruibai.vendor
 * Date: 2022/11/10 09:47
 */
public class Solution_371 {

    static Solution_371 instance = new Solution_371();

    public static void main(String[] args) {
        int a = 3;
        int b = 5;
        System.out.println(instance.getSum(a, b));
    }

    public int getSum(int a, int b) {
        /**
         * a+b=a ^ b + ((a & b) << 1)
         * 但是，上面有"+"
         * 所以为了防止有"+"或者"-"，需要继续递归
         * 直到(a&b)<<1=0 即 b=0
         */
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

}
